#include "predicate.h"
#include <limits>
#include <cmath>
#include <algorithm>
#include <gmpxx.h> 

#ifndef GMP_PRECISION
#define GMP_PRECISION 128
#endif

bool operator<(const Point &p1, const Point &p2)
{
	return p1.x == p2.x ? p1.y < p2.y : p1.x < p2.x;
}

bool operator==(const Point &p1, const Point &p2)
{
	return p1.x == p2.x && p1.y == p2.y;
}

bool operator!=(const Point &p1, const Point &p2)
{
	return !(p1 == p2);
}

namespace std {
	ostream& operator<<(ostream &s, const Point &a) 
	{
		return s << a.x << " " << a.y;
	}

	template<>
	void swap(Point &a, Point &b)
	{
		std::swap(a.x, b.x);
		std::swap(a.y, b.y);
	}
}
	
const double EPS = std::numeric_limits<double>::epsilon();

template <typename T>
int sign(T a) 
{
	return a == 0 ? 0 : (a > 0 ? 1 : -1);
}

int gmp_left_turn(
        const mpf_class &ax, const mpf_class &ay,
        const mpf_class &bx, const mpf_class &by,
        const mpf_class &cx, const mpf_class &cy)
{
	mpf_class res(0, GMP_PRECISION);
	res = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
	
	return sign(res);
}

int left_turn(const Point &a, const Point &b, const Point &c)
{
	double err = 4 * EPS * (abs((b.x - a.x) * (c.y - a.y)) + abs((b.y - a.y) * (c.x - a.x)));
	double res = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);

	if (abs(res) > err) 
	{
		return sign(res);
	}
	else 
	{
		return gmp_left_turn(a.x, a.y, b.x, b.y, c.x, c.y);
	}
}

int gmp_closer(	
        const mpf_class &lax, const mpf_class &lay,
        const mpf_class &lbx, const mpf_class &lby,
        const mpf_class &ax, const mpf_class &ay,
        const mpf_class &bx, const mpf_class &by)
{
	mpf_class res(0, GMP_PRECISION);
	res = (lay - lby) * (ax - bx) - (lax - lbx) * (ay - by);

	return sign(res);
}

int closer(const Line &l, const Point &a, const Point &b) {
	double err = 8 * EPS * (abs(l.a.x * a.y) + abs(l.a.x * b.y) + abs(l.b.x * a.y) + abs(l.b.x * b.y) +
		abs(l.a.y * a.x) + abs(l.a.y * b.x) + abs(l.b.y * a.x) + abs(l.b.y * b.x));
	double res = (l.a.y - l.b.y) * (a.x - b.x) - (l.a.x - l.b.x) * (a.y - b.y);

	if (abs(res) > err) 
	{
		return sign(res);
	}
	else 
	{
		return gmp_closer(l.a.x, l.a.y, l.b.x, l.b.y, a.x, a.y, b.x, b.y);
	}
}

int get_y_gmp(
        const mpf_class &p1x, const mpf_class &p1y,
        const mpf_class &p2x, const mpf_class &p2y,
        const mpf_class &x, const int y, bool &exact) // answer is y-1 or y or y+1
{
	mpf_class res(0, GMP_PRECISION);
	res = p1y + (x - p1x) * (p2y - p1y) / (p2x - p1x);

	exact = floor(res) == res;

	if (res >= y + 1) return y + 1;
	if (res >= y) return y;
	return y - 1;
}

int get_max_y(const Point &p1, const Point &p2, int x1, int x2, bool &exact)
{
	exact = false;
	double xx1, xx2, dy1, dy2;
	bool exact1 = false, exact2 = false;

	if (x1 > p1.x)
	{
		xx1 = x1;
		dy1 = (x1 - p1.x) * (p2.y - p1.y) / (p2.x - p1.x);
	}
	else
	{
		xx1 = p1.x;
		dy1 = 0;
		exact1 = true;
	}

	if (x2 < p2.x)
	{
		xx2 = x2;
		dy2 = (x2 - p1.x) * (p2.y - p1.y) / (p2.x - p1.x);
	}
	else
	{
		xx2 = p2.x;
		dy2 = p2.y - p1.y;
		exact2 = true;
	}

	if (dy1 > dy2 && exact1)
	{
		exact = p1.y == std::floor(p1.y);
		return std::floor(p1.y);
	}
	if (dy1 <= dy2 && exact2)
	{
		exact = p2.y == std::floor(p2.y);
		return std::floor(p2.y);
	}

	double y = std::max(dy1, dy2) + p1.y, err = EPS * 4 * y;
	int res = std::floor(y);
	if (res < y - err && res + 1 > y + err) {
		return res;
	}
	return get_y_gmp(p1.x, p1.y, p2.x, p2.y, dy1 > dy2 ? xx1 : xx2, res, exact);
}

int get_min_y(const Point &p1, const Point &p2, int x1, int x2, bool &exact) 
{
	exact = false;
	double xx1, xx2, dy1, dy2;
	bool exact1 = false, exact2 = false;

	if (x1 > p1.x)
	{
		xx1 = x1;
		dy1 = (x1 - p1.x) * (p2.y - p1.y) / (p2.x - p1.x);
	}
	else
	{
		xx1 = p1.x;
		dy1 = 0;
		exact1 = true;
	}

	if (x2 < p2.x)
	{
		xx2 = x2;
		dy2 = (x2 - p1.x) * (p2.y - p1.y) / (p2.x - p1.x);
	}
	else
	{
		xx2 = p2.x;
		dy2 = p2.y - p1.y;
		exact2 = true;
	}

	if (dy1 < dy2 && exact1)
	{
		exact = p1.y == std::floor(p1.y);
		return std::floor(p1.y);
	}
	if (dy1 >= dy2 && exact2)
	{
		exact = p2.y == std::floor(p2.y);
		return std::floor(p2.y);
	}

	double y = std::min(dy1, dy2) + p1.y, err = EPS * 4 * y;
	int res = std::floor(y);
	if (res < y - err && res + 1 > y + err) {
		return res;
	}
	return get_y_gmp(p1.x, p1.y, p2.x, p2.y, dy1 < dy2 ? xx1 : xx2, res, exact);
}